package 每日一题;

/**
 * 1089. 复写零
 * 给你一个长度固定的整数数组 arr，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。
 *
 * 注意：请不要在超过该数组长度的位置写入元素。
 *
 * 要求：请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。
 *
 *
 *
 * 示例 1：
 *
 * 输入：[1,0,2,3,0,4,5,0]
 * 输出：null
 * 解释：调用函数后，输入的数组将被修改为：[1,0,0,2,3,0,0,4]
 * 示例 2：
 *
 * 输入：[1,2,3]
 * 输出：null
 * 解释：调用函数后，输入的数组将被修改为：[1,2,3]
 */
public class D220617_T1089 {
    //先遍历 数字 统计0 的个数 ，计算新数组的末尾 从后往前遍历
    public void duplicateZeros(int[] arr) {

        int count0 = 0;
        int countNo0 = 0;
        int length = arr.length;
        int index = 0;

        for (int j : arr) {

            if (countNo0 + (2 * count0) >= length) {
                break;
            }

            if (j == 0) {
                count0 = count0 + 1;
            } else {
                countNo0 = countNo0 + 1;
            }


        }


        int lastIndex = length - 1; //记录从后往前排的坐标
        index = count0 + countNo0 - 1;
        if (countNo0 + (count0 * 2) > arr.length) { //最后一位是单个0
            arr[lastIndex] = 0;
            lastIndex = lastIndex - 1;
            index = index - 1;
        }


        for (int i = index; i >= 0; i--) {
            if (arr[i] == 0) { //把当前及前一个 元素置位0
                arr[lastIndex] = 0;
                arr[lastIndex - 1] = 0;
                lastIndex = lastIndex - 2;
            } else {//将当前的元素 从后往前排
                arr[lastIndex] = arr[i];
                lastIndex = lastIndex - 1;
            }
        }


    }

    public static void main(String[] args) {
        D220617_T1089 d220617_t1089 = new D220617_T1089();
        int[] ints = {1, 0, 2, 3, 0, 4, 5, 0};
        d220617_t1089.duplicateZeros(ints);
        System.out.println(ints);
    }
}
